#include <iostream>

using namespace std;

bool func1(string s, string p) {
    int n = s.size(), m = p.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    dp[0][0] = 1;

    // 空串被 a*, a*b* ... 匹配
    for (int j = 2; j <= m; ++j)
        if (p[j-1] == '*') dp[0][j] = dp[0][j-2];

    auto same = [&](char a, char b){ return a == b || b == '.'; };

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (p[j-1] != '*') {
                if (same(s[i-1], p[j-1]))
                    dp[i][j] = dp[i-1][j-1];
            } else {
                // '*' 匹配 0 次
                dp[i][j] = dp[i][j-2];
                // '*' 匹配 >=1 次
                if (same(s[i-1], p[j-2]))
                    dp[i][j] = dp[i][j] || dp[i-1][j];
            }
        }
    }
    return dp[n][m];
}

vector<int> palindromeStarts(const vector<int>& nums, int k) {
    vector<int> ans;
    int n = nums.size();
    if (k <= 0 || k > n) return ans;
    for (int i = 0; i + k <= n; ++i) {
        int l = i, r = i + k - 1;
        bool ok = true;
        while (l < r) {
            if (nums[l] != nums[r]) { ok = false; break; }
            ++l; --r;
        }
        if (ok) ans.push_back(i);
    }
    return ans;
}

#include <bits/stdc++.h>
using namespace std;

vector<int> func2(const vector<int>& nums, int k) {
    vector<int> ans;
    int n = nums.size();
    if (k <= 0 || k > n) return ans;

    for (int i = 0; i + k <= n; i++) {
        string s;
        for (int j = i; j < i + k; j++) {
            s += to_string(nums[j]);
        }
        string rev = s;
        reverse(rev.begin(), rev.end());
        if (s == rev) ans.push_back(i);
    }
    return ans;
}



struct Edge {
    int to, bw, delay;
};

int func3(int n, int s, int t,
                        vector<int>& node_bandwidths,
                        vector<vector<int>>& edges,
                        int d) {
    // 构建图（先过滤节点和边）
    vector<vector<Edge>> graph(n);
    vector<bool> valid_node(n, false);
    for (int i = 0; i < n; i++) {
        if (node_bandwidths[i] >= d) valid_node[i] = true;
    }

    for (auto& e : edges) {
        int u = e[0], v = e[1], bw = e[2], delay = e[3];
        if (bw >= d && valid_node[u] && valid_node[v]) {
            graph[u].push_back({v, bw, delay});
            graph[v].push_back({u, bw, delay}); // 无向图
        }
    }

    // 如果源点或目标点无效，直接返回 -1
    if (!valid_node[s] || !valid_node[t]) return -1;

    // Dijkstra
    vector<int> dist(n, INT_MAX);
    dist[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [dcur, u] = pq.top(); pq.pop();
        if (dcur > dist[u]) continue;
        for (auto& e : graph[u]) {
            int v = e.to;
            int nd = dcur + e.delay;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }

    return dist[t] == INT_MAX ? -1 : dist[t];
}